import copy


class Solution(object):
    def profitableSchemes(self, n, minProfit, group, profit):
        base = 10 ** 9 + 7
        m = len(group)
        DP = [[0 for _ in range(n + 1)] for _ in range(minProfit + 1)]
        DP[0][0] = 1
        ans = 0
        if minProfit == 0:
            ans = 1
        for i in range(m):
            next_DP = copy.deepcopy(DP)
            for j in range(minProfit + 1):
                for k in range(n + 1 - group[i]):
                    if DP[j][k] > 0:
                        if j + profit[i] >= minProfit:
                            ans = (ans + DP[j][k]) % base
                            next_DP[minProfit][k + group[i]] = (next_DP[minProfit][k + group[i]] + DP[j][k]) % base
                        else:
                            next_DP[j + profit[i]][k + group[i]] += DP[j][k]
                            next_DP[j + profit[i]][k + group[i]] %= base
            DP = next_DP
        return ans


data = Solution()
# n = 5
# minProfit = 3
# group = [2, 2]
# profit = [2, 3]
# print(data.profitableSchemes(n, minProfit, group, profit))
# n = 10
# minProfit = 5
# group = [2, 3, 5]
# profit = [6, 7, 8]
# print(data.profitableSchemes(n, minProfit, group, profit))
n = 64
minProfit = 0
group = [80, 40]
profit = [88, 88]
print(data.profitableSchemes(n, minProfit, group, profit))
